一道简单的算法题,要求在数组中,找到所有和为定值的数组对。比如在array(11,11,1,2,-1,3,4,6,7,8,9,5,-1)中,找到所有和为10的数组对。
考虑到时间复杂度,牺牲空间,每个值作为一个key,他的互补对为value-key,每遍历一个数组值,先判断有没有互补对,有则打印此key,和互补key,互补key-1,否则添加一个key.php代码如下:
<?php function findSum($arr, $sum) { $total = 0; $sumArr = array(); foreach($arr as $key) { //如果有此key,并且有和为sum的key,总数加一,失去一个互补key if(isset($sumArr[$sum-$key]) && ($sumArr[$sum-$key] > 0)) { $total ++ ; //打印出来 $diff = $sum-$key; echo "($key, $diff)</br>"; //互补key -1 $sumArr[$sum-$key] --; }else{ //添加一个key isset($sumArr[$key]) ? $sumArr[$key]++ : ($sumArr[$key] = 1); } } echo "total:{$total}"; } //测试用例 $arr = array(11,11,1,2,-1,3,4,6,7,8,9,5,-1); findSum($arr, 10);
测试结果为:
(-1, 11)
(6, 4)
(7, 3)
(8, 2)
(9, 1)
(-1, 11)
total:6